Virtually all data processing systems employ operating systems for proper allocation and disposition of data processing resources and for the scheduling and management of work in the system. One of the more widely used operating systems is MVS, or "Multiple Virtual Storage". That operating system has been employed in the 370 and 390 series of computers marketed by the International Business Machines Corporation, assignee of this application. One feature of MVS is its ability to create variable size virtual storage areas and to allocate them to various users, tasks and resource suppliers. As is known, virtual storage gives programmers the appearance of a very large amount of storage at their disposal. Since most programs generally need only a fraction of main memory at any given time, portions of main memory (also called real storage) are allocated as necessary by the operating system to achieve efficient program execution. Underlying hardware maps addresses in virtual storage to locations in real storage, and automatically translates those addresses during program execution. When blocks of real storage (called pages) are determined to be not needed for immediate use, they are written out and saved on external storage media and the real storage frames are made available for use by other programs. The saved pages are later read back into real storage only when referenced by the associated program.
Such a system will be better understood by referring to FIG. 1 where it is assumed that two application programs (i.e., A and C) have been assigned virtual address spaces 10 and 12, respectively. The boxes indicated by numbers 10 and 12 are only for explanatory purposes and are not to be assumed as defining physical constraints.
Each virtual address space in MVS is represented by an Address Space Control Block (ASCB) that contains system data describing status of an associated virtual storage area. An ASCB will contain, for example, an indication of the assigned priority of its associated virtual address space and whether any work units within it are available for dispatch.
From an examination of FIG. 1, it can be seen that dispatchable work units B and D are assigned (by MVS) the priority of virtual address space 14, notwithstanding the fact that dispatchable unit B resulted from a work request originating out of virtual address space 10, while dispatchable unit D resulted from a work request originating out of virtual address space 12. For this example, virtual address space 10 is assigned an arbitrary low priority whereas virtual address space 12 is assigned an arbitrary higher priority. For work units B and D, those priorities are not considered by MVS since it automatically assigns to a dispatchable unit, the priority of the Home address space in which the unit of work executes. As a consequence, dispatchable units are dispatched only after their Home address space becomes the highest priority address space in the data processing system.
In general, dispatch of ready work units in MVS is carried out by a dispatcher component of the operating system. The priority by which control is routed to each ready work unit is controlled first by the priority assigned to the Home address space of each work unit and then by the position that work unit occupies in the linked list of Task Control Blocks (TCBs) chained from the ASCB for their Home address space. More specifically, work is dispatched in the following order:
1. Exits to routines having high priority because of specific conditions in the system. PA1 2. SRBs that have global priority. An SRB (Service Request Block) is a system scheduler control block. PA1 3. Ready address spaces in order of priority.
(a) Local SRBs scheduled for execution to a chosen address space PA2 (b) Ready TCBs according to task priority within the chosen address space.
Underlying structures supporting priority dispatching in MVS include a linked list of ASCBs with ready work. The linked list is called the True Ready Queue. The position each ASCB occupies on this list is determined by its assigned address space priority. The first ASCB 32 shown on the True Ready Queue in FIG. 2 represents a system address space called the MVS "Master" address space which is given the highest address space priority in the system. Certain high priority, system level work is scheduled for execution in this address space. The Master address space is selected first by the dispatcher 30 whenever it has ready work to dispatch. When all ready work in the Master address space has been dispatched and completed, ASCB 32 for Master is removed from the True Ready Queue and the dispatcher selects the new highest priority address space having work ready for dispatch. This is shown as ASCB 16 in FIG. 2 where tasks TCB 18 and TCB 20 are found to be ready for dispatch. The dispatcher then selects and routes control to the ready TCB having the highest task priority within the address space represented by ASCB 16.
The intent of the MVS priority allocation system can be substantially frustrated where work from a high priority application is performed in an address space having a low priority. In such case, the work unit must wait for the low priority address space to become the highest priority awaiting dispatch, thus holding up further processing of the high priority application.
Other priority problems are present within MVS. Highly used system functions that serialize certain operations via locks (allow only one access at a time) are sometimes called by low priority users. When the low priority user accesses the highly used system function, a "lock" may be assigned to the low priority user temporarily blocking other users accessing the same system function. If the low priority user is interrupted while holding the "lock", the lock may not be freed and reassigned for an extended period of time, due to the low priority of the lock holder. During this time, higher priority users, also requesting services of the same system function, are placed on a queue and are suspended, pending availability of the lock. Thus, the use of locks can disrupt the normal processing flow intended by priority dispatching and may, in certain cases become a serious bottleneck in the system. In addition, where applications are distributed among various processors in a multi-processor arrangement, it is difficult, using MVS, to support a single, common dispatching priority for all component work units of the distributed application.
The prior art contains many different priority allocation schemes. In U.S. Pat. No. 4,394,730 to Suzuki et al., processors in a multiprocessor system are arranged in a predetermined priority sequence and, in response to an interrupt command, the system always directs a transferred job to a priority processor whose currently executing job is, in turn, transferred to a lower priority processor. In U.S. Pat. Nos. 4,286,322 and 4,394,727, both to Hoffman et al., prioritization schemes are described based on partitioning of high priority system work from other less important application work. System work is preemptive and is dispatched from a prime task dispatcher queue. Application work is non preemptive and is dispatched from non-prime (secondary) task dispatcher queues. In the '727 patent, Hoffman et al. describe a system where dispatching occurs from a single dispatching queue. A dispatcher is defined for each processor and is invoked in response to the queueing of an element in the dispatching queue. The dispatching queue is scanned for work having higher priority than currently is being processed by other processors. The dispatcher then signals the task dispatcher of a processor that is either idle, or running lower priority work to perform a task switch.
Sherrod, in U.S. Pat. No. 4,642,756, describes a scheduling and dispatching mechanism meant to deal with response/oriented applications such as real time or interactive processing, while also maximizing usage of the central processing unit and peripheral devices. The system deals with static, externally assigned priorities and internally assigned, dynamic priorities depending on the state of each task.
In U.S. Pat. No. 4,736,318 to Delyani et al., dispatching is based on task priority, with dispatched tasks running until they voluntarily give up control or run out of time within which the task may execute. The dispatch priority of a task is automatically adjusted up or down based on the behavior of the task (e.g., whether CPU bound or I/O bound), stopping higher priority CPU-bound tasks from completely blocking the execution of lower priority I/O bound tasks.
Jablow, in U.S. Pat. No. 4,908,750, describes a similar system to that described by Delyani et al., in that tasks that make requests for I/O or other services are given raised dispatching priority and are also given a complete execution time slice, (instead of the remaining time left from their interrupted interval). This compensates for voluntarily giving up the CPU and waiting for a requested event to complete.
Clark, in U.S. Pat. No. 4,943,913, describes a mechanism in MVS that provides easy accessibility to private storage in the home address of a currently dispatched execution unit, without having to modify CPU status or pointers to any other address spaces.
The following IBM Technical Disclosure Bulletin references also indicate various prior art priority schemes: Abraham, "Priority Scheduling on a Multi-Level Computer", IBM TDB, Vol. 21, No. 11, April 1979; Solly, "Avoiding Deadlock in a Message-Passing Control Program", IBM TDB, Vol. 28, No. 5, October 1985; and Brown et al., "Proportional Rates Scheduling Mechanism", IBM TDB Vol. 19, No. 11, April 1977.
Accordingly, it is an object of this invention to provide an improved dispatching priority system.
It is another object of this invention to provide an improved dispatching priority system which provides the capability for dispatchable units to be dispatched with the priority of the requesting task's originating address space.
It is yet another object of this invention to provide a dispatching priority system which assures that a lower priority task holding a lock will not seriously delay the processing of a higher priority task.
It is still another object of this invention to provide improved priority dispatching in a multiprocessing system where coupled individual processors cooperatively run under control of separate operating systems.